/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：猜数字大小 II</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/
 * </pre>
 * <p>创建日期：2019年12月5日下午2:43:39</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code375GuessNumberHigherOrLowerii</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code375GuessNumberHigherOrLowerii
{
	public static void main(String[] args)
	{
		/**
		 * 我们正在玩一个猜数游戏，游戏规则如下：

		我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

		每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

		然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

		示例:

		n = 10, 我选择了8.

		第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
		第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
		第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

		游戏结束。8 就是我选的数字。

		你最终要支付 5 + 7 + 9 = 21 块钱。
		给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

		 */
		int moneyAmount = getMoneyAmount(10);
		System.out.println(moneyAmount);
	}

	public static int getMoneyAmount(int n)
	{
		//dp[i][j]表示第一次选数字j猜中数字i所需要的现金数,当i==j时，属于猜中
		/**
		 * int[][] dp = new int[n+1][n+1]
		 * dp[0][0]=0
		 * dp[1][0]=0
		 */
		int[][] dp = new int[n + 1][n + 1];
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				if (i == 0 || j == 0)
				{
					dp[i][j] = -1;
				}
				if (i == j)
				{
					dp[i][j] = 0;
				}
			}
		}
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println();
		}
		System.out.println();
		return -1;
	}
}
